#define DEBUG
#include <cstdio>

using namespace std;

const int maxk=200, mods=998244353;

class Matrix {
public:
  int n, m;
  long long a[maxk+1][maxk+1];

  void mul(Matrix *x, Matrix *y, int mods) {
    if (x->m!=y->n) {
      throw -1;
    }
    n = x->n, m = y->m;
    for (int i=0; i<n; i++) {
      for (int j=0; j<m; j++) {
	a[i][j] = 0;
	for (int k=0; k<x->m; k++) {
	  a[i][j] = (a[i][j]+x->a[i][k]*y->a[k][j]%mods)%mods;
	}
      }
    }
  }
};

long long qpower(long long a, int n, int mods) {
  long long s=1;
  for (; n>1; n/=2) {
    if (n%2) {
      s = s*a%mods;
    }
    a = a*a%mods;
  }
  return s*a%mods;
}

long long solve1(int n, int k, int *b, long long *t) {
  const int maxn=40000000;
  static long long f[maxn+1];
  for (int i=1; i<=k; i++) {
    f[i] = t[i];
  }
  for (int i=k+1; i<=n; i++) {
    f[i] = 1;
    for (int j=1; j<=k; j++) {
      f[i] = f[i]*qpower(f[i-j], b[j], mods)%mods;
    }
  }
  return f[n];
}

long long solve2(int n, int k, long long *t) {
  const int maxn=1000000;
  static long long f[maxn+1];
  f[k+1] = 1;
  for (int i=1; i<=k; i++) {
    f[i] = t[i];
    f[k+1] = f[k+1]*t[i]%mods;
  }
  for (int i=k+2; i<=n; i++) {
    f[i] = f[i-1]*f[i-1]%mods*qpower(f[i-k-1], mods-2, mods)%mods;
  }
  return f[n];
}

long long solve3(int n, int k, int *b, long long *t) {
  return 0;
}

int main() {
  freopen("seq.in", "r", stdin);
  freopen("seq.out", "w", stdout);

  static int b[maxk+1];
  static long long f[maxk+1];
  int n, k;
  bool flag=true;
  scanf("%d %d", &n, &k);
  for (int i=1; i<=k; i++) {
    scanf("%d", b+i);
    flag = flag && b[i]==1;
  }
  for (int i=1; i<=k; i++) {
    scanf("%lld", f+i);
  }

  if (n<=10000) {
    printf("%lld", solve1(n, k, b, f));
  } else if (flag && n<=1000000) {
    printf("%lld", solve2(n, k, f));
  } else {
    printf("%lld", solve1(n, k, b, f));
  }
    
  fclose(stdin);
  fclose(stdout);
  return 0;
}
